A content addressable memory (CAM) device is a storage device having an array of memory cells that can be instructed to compare the specific pattern of an input string (e.g., a search key or a comparand word) with data stored in rows of the array. The entire CAM array, or segments thereof, may be searched in parallel for a match with the comparand data. If a match exists, the CAM device indicates the match condition by asserting a match flag, and may indicate the existence of multiple matches by asserting a multiple match flag. The CAM device typically includes a priority encoder that determines the highest priority matching address (e.g., the lowest matching CAM index). The highest priority matching (HPM) address, the contents of the matched location, and other status information (e.g., skip bit, empty bit, full flag, as well as match and multiple match flags) may be output from the CAM device to an output bus. In addition, associative data may be read out from an associated addressable storage device (e.g., DRAM).
To increase bandwidth, it is desirable for CAM devices to handle multiple flows (e.g., different input strings) at the same time. This can be achieved using a CAM array having rows of multi-compare CAM cells that can compare multiple input strings with stored data therein at the same time. For conventional multi-compare CAM arrays, the match results associated with respective multiple compare operations are provided simultaneously to a single priority encoder, which in turn generates the HPM index. Because conventional priority encoders generate the HPM index as a function of priority (e.g., the physical location of the matching data relative to the non-matching data), the output match results of one flow can dominate the output match results of other flows depending upon the arrangement of data stored in the CAM device. For example, if input strings associated with a first flow F1 most frequently match higher-priority CAM data and input strings associated with a second flow F2 most frequently match lower-priority CAM data, then the priority encoder will most frequently report the match results (i.e., the HPM indices) of the first flow F1, even if the second flow F2 also has match conditions during the same compare cycle. In this case, the match results of the first flow F1 override the match results of the second flow F2, thereby unfairly rendering the accuracy of the second flow's match results subject to the match results of the first flow. Indeed, the preferential reporting of match results for one flow over the match results of other flows is not acceptable in multi-flow search systems for which multiple flows are deemed to be equally important (e.g., such as those currently employed in QoS functions, regular expression searching, intrusion detection, and so on).
The problem of under-reporting the match results of some flows in favor of the match results of another flow can be addressed by providing a separate priority encoder for each flow to be simultaneously compared in the CAM device. However, because priority encoders are complex logic circuits having a number of hierarchical levels of logic gates, providing a separate priority encoder for each flow in a multi-flow CAM device would dramatically increase the size and power consumption of the CAM device.
Thus, there is a need for a flow-sensitive priority encoding scheme for a CAM device that ensures an even distribution of match results between multiple flows without requiring a separate priority encoder for each flow.
Like reference numerals refer to corresponding parts throughout the drawing figures.